package com.huawei;


import com.huawei.deployentity.CandidateDeployServer;
import com.huawei.deployentity.DeployServer;
import com.huawei.deployentity.DeployVM;
import com.huawei.inputentity.Require;
import com.huawei.inputentity.Server;
import com.huawei.inputentity.VisualMachine;

import java.io.FileNotFoundException;
import java.util.*;
import java.util.function.Predicate;

public class Main {
    static List<Output> outputList = new ArrayList<>();//每天输出列表
    static Output dailyOutPut;

    static List<DeployVM> deployVMList=new LinkedList<>();//记录所有已经添加过的虚拟机（方便执行删除操作）
    static List<DeployServer> deployServerList=new LinkedList<>();//记录所有购买的服务器

    static long totalId;//分配服务器id

    public static void main(String[] args) throws FileNotFoundException {

        //本地测试数据
        String pathName = "src/com/huawei/my_tain1.txt";
//        String[] arr = Input.readFile(pathName);

        //标准输入数据
        String[] arr = Input.readStdIn();
        Input.resolve(arr);
        process();

        //题目要求的最终输出结果
        for (int i=0;i< outputList.size();i++){
//            System.out.println("=============day "+i+"=============");
            Output dailyOutPut=outputList.get(i);
            dailyOutPut.result();
        }

        //查看统计数据
//        long totalCost=0;//记录总花销
//        for (DeployServer deployServer:deployServerList){
//            totalCost = Math.addExact(totalCost,deployServer.getHardWareCost());
//        }
//        for (int i=0;i< outputList.size();i++){
//            System.out.println("=============day "+i+"=============");
//            Output dailyOutPut=outputList.get(i);
//            long dailyRestCpu=0,dailyRestMemory=0;
//            long dailyCost=0;
//            for (DeployServer deployServer: dailyOutPut.getDailyDeployServer()){
//                dailyCost=Math.addExact(dailyCost,deployServer.getDailyCost());
//                dailyRestCpu=Math.addExact(dailyRestCpu,deployServer.getNodeARestCPU()+deployServer.getNodeBRestCPU());
//                dailyRestMemory=Math.addExact(dailyRestMemory,deployServer.getNodeARestMemory()+deployServer.getNodeBRestMemory());
//            }
//            dailyCost = Math.multiplyExact(dailyCost,outputList.size()-i);
//            totalCost=Math.addExact(totalCost,dailyCost);
//            System.out.printf("当天购买服务器剩余资源统计：cpu:%d, memory:%d  当天购买的服务器总数%d，当天部署的虚拟机总数%d\n",
//                    dailyRestCpu,dailyRestMemory,dailyOutPut.getDailyDeployServer().size(),dailyOutPut.getDailyDeployVM().size());
//
//        }
//        System.out.println("总花费："+totalCost);
//        int totalRestCpu=0,totalRestMemory=0;
//        for (DeployServer deployServer:deployServerList){//当天运行中服务器剩余资源
//            totalRestCpu=Math.addExact(totalRestCpu,deployServer.getNodeARestCPU()+deployServer.getNodeBRestCPU());
//            totalRestMemory=Math.addExact(totalRestMemory,deployServer.getNodeARestMemory()+deployServer.getNodeBRestMemory());
//        }
//        System.out.printf("服务器资源总剩余：cpu:%d  memory:%d",totalRestCpu,totalRestMemory);

    }

    //思路参考：https://blog.csdn.net/weixin_44459972/article/details/114756490
    static void process(){
        //1.将服务器分类，先分为核内比大于1和小于1的
        List<Server> greaterThanOnes = new ArrayList<>();//核内比大于一，且按照costPerformance（性价比）升序排序
        List<Server> lessThanOnes = new ArrayList<>();//核内比小于等于一
        classifyServer(greaterThanOnes,lessThanOnes);

        //以天为单位遍历
        // TODO: 2021/3/16 暂时只看前10天的，最终应该是i<Input.dailyRequireList.size()
        for (int i=0;i<Input.dailyRequireList.size();i++){
            //每天一个新的output
            dailyOutPut =new Output(i);

            // TODO: 2021/3/16 每次到了5n/1000 ！= 0 && 移动的虚拟机可以空出>=1台服务器时移动（根据剩余资源差值最小+和最小排序）
            int totalMigrate = deployVMList.size()/200;//每天能够迁移的虚拟机上限
            List<Require> delRequireList = Input.dailyRequireList.get(i).get("delList");//每天的删除请求
            List<Require> addRequireList = Input.dailyRequireList.get(i).get("addList");//每天的add请求



            //处理每天的add请求
            double averageRatio=averageRequiresRatio(addRequireList);//当日的平均核内比
//            System.out.println(averageRatio);
            //2.将一天的请求分类为单节点部署和双节点部署，这里暂时用第一天的数据做测试
            List<Require> singleNodeList = new ArrayList<>();
            List<Require> doubleNodeList = new ArrayList<>();
            doubleOrSingle(addRequireList,singleNodeList,doubleNodeList);

            //3.分别singleNodeList和doubleNodeList执行购买并部署
            //将每天的add请求分为双节点和单节点的，再根据平均核内比分配相应的服务器。
            //有点分治的思维
            if (averageRatio>1){
                // TODO: 2021/3/16 降序还是升序？在斟酌一下
                //将当日的单、双节点的请求按照cpu降序排序
                singleNodeList.sort((o1, o2) -> o2.getVm().getCPU()-o1.getVm().getCPU());
                doubleNodeList.sort((o1, o2) -> o2.getVm().getCPU()-o1.getVm().getCPU());
                distribute(doubleNodeList,greaterThanOnes);//用核内比大于一的服务器
                distribute(singleNodeList,greaterThanOnes);

            }else {
                singleNodeList.sort((o1, o2) -> o2.getVm().getMemory()-o1.getVm().getMemory());
                doubleNodeList.sort((o1, o2) -> o2.getVm().getMemory()-o1.getVm().getMemory());
                distribute(doubleNodeList,lessThanOnes);//用核内比小于一的服务器
                distribute(singleNodeList,lessThanOnes);

            }

            //处理每天的del请求，应该先处理del请求再处理add请求，因为可能会发生当天添加又删除的情况
            for (Require delRequire:delRequireList){
                DeployVM deployVM = null;
                for(DeployVM d:deployVMList){//找到该删除请求对应的虚拟机
                    if (d.getId()==delRequire.getVMId()) deployVM=d;
                }
                DeployServer deployServer = deployVM.getDeployServer();//该虚拟机部署到的服务器
                deployServer.releaseVM(deployVM);//释放资源
                deployVMList.removeIf(deployVM1 -> deployVM1.getId() == delRequire.getVMId());//删除该虚拟机
            }

            //每天结束后添加每天的部署和购买服务器信息
            outputList.add(dailyOutPut);

        }
    }


    /**
     * 部署虚拟机
     * 外层当天请求列表，不为空进行下面的步骤
     * 内层deployServer列表，如果为空，则新增server
     * 首先从deployServer列表中找到能够部署的节点，这是现有已经购买的服务器，
     * 如果找不到这样的节点，则在serverList中遍历，找到第一个合适的server，加入到deployServer列表中（找第一个是保证了性价比最高）
     * 删除当前处理的require
     */
    static void distribute(List<Require> requireList, List<Server> serverList){
        //case1 遍历请求，寻找能够部署的**已有**服务器，若能够找到则部署，否则执行case2
        Iterator<Require> iterator = requireList.listIterator();

        for (int i= requireList.size()-1;i>=0;i--){
            Require require= requireList.get(i);
            boolean state=false;
            //找到能够满足require的**已有**服务器
            for (DeployServer deployServer:deployServerList){
                String node = isDeployable(require,deployServer);
                if (node==null||node.length()==0) continue;//该服务器无法部署，继续找
                //该虚拟机请求可以部署到目标服务器
                DeployVM deployVM = deployVM(require,deployServer,node);
                deployVMList.add(deployVM);//分配完毕，添加当前虚拟机到列表中
                dailyOutPut.addDailyDeployVM(deployVM);
                //部署成功，删除当前请求
                requireList.remove(require);
                state=true;
                //当前请求处理完毕，处理下一个请求
                break;
            }

            if (state) continue;//表明已经找到满足的服务器了，不需要新找了，处理下一个请求

            //case2 已有服务器不能满足要求，**新购买**一台服务器。注意这个新购买的服务器需要加入到deployServerList中
            //优化：新购买的服务器采用优化算法SelectCandidateServer。总的思路是：
            // 1.获取这个候选的服务器；2.获取这个候选服务器的拟部署的虚拟机列表；3.将这些虚拟机请求部署到该服务器上（这些步骤似乎可以直接跳过）
            // 4.将这些虚拟机列表上对应的请求删除

            CandidateDeployServer newDeployServer = selectCandidateServer(serverList,requireList);
            deployServerList.add(newDeployServer);
            dailyOutPut.addDailyDeployServer(newDeployServer);
            //deployVMList添加新虚拟机，然后从requireList中删除这些请求
            for (DeployVM deployVM:newDeployServer.getDeployVMDistributeList()){
                //添加虚拟机
                deployVMList.add(deployVM);
                dailyOutPut.addDailyDeployVM(deployVM);
                //删除请求，这里应该批量删除，得用iterator一个一个删
                requireList.removeIf(new Predicate<Require>() {
                    @Override
                    public boolean test(Require require) {
                        return deployVM.getId() == require.getVMId();
                    }
                });
            }
            i= requireList.size();
        }
    }

    // TODO: 2021/3/17 这里可以优化一下算法：采用01背包问题，遍历所有服务器类型，
    //  对于requireList，采用01背包思想装进服务器中，然后再选择资源指标最少的作为返回值
    /**
     * 算出一个最合适的服务器，以及它处理的请求
     */
    static CandidateDeployServer selectCandidateServer(List<Server> serverList, List<Require> requireList){
        requireList =  new ArrayList<>(requireList);//感觉需要重新给这个列表分配地址，因为这里是模拟删除操作，不要影响原来的请求列表
        List<CandidateDeployServer> candidateDeployServerList = new ArrayList<>();
        for (Server server:serverList){
            CandidateDeployServer candidateDeployServer = new CandidateDeployServer(server);
            Iterator<Require> iterator = requireList.listIterator();
            while (iterator.hasNext()){
                Require require = iterator.next();
                String node = isDeployable(require,candidateDeployServer);
                if (node==null||node.length()==0) continue;//该请求无法部署上去
                DeployVM deployVM = deployVM(require,candidateDeployServer,node);
                candidateDeployServer.addDeployVMDistributeList(deployVM);
                // TODO: 2021/3/16 从列表中删除该require (finish)
                iterator.remove();
            }
            //该候选服务器组合完毕，加入到列表中。有可能并没有加入请求，所以需要加判断
            if (candidateDeployServer.getDeployVMDistributeList().size()!=0)
                candidateDeployServerList.add(candidateDeployServer);
        }
        //将候选服务器列表按照剩余资源升序排序，选取第一个返回
        candidateDeployServerList.sort(new Comparator<CandidateDeployServer>() {
            @Override
            public int compare(CandidateDeployServer o1, CandidateDeployServer o2) {
                return o1.getRestResource()-o2.getRestResource();
            }
        });
        //差点忘了，要设置id!!1
        CandidateDeployServer server = candidateDeployServerList.get(0);
        server.setId(generateId());
        return server;
    }


    /**
     * 部署虚拟机<br/>
     * 需要进行的步骤 （因为在调用此方法之前会调用{@link #isDeployable(Require, DeployServer)}所以一定能够部署的）<br/>
     * 实现将require对应的虚拟机部署到一个服务器上：<br/>
     * 1.根据A、B、AB节点减少DeployServer对象相应节点的资源（CPU和memory）<br/>
     * 2.创建deployVM，添加其id、所属虚拟机、部署到的服务器（deployServer）、节点<br/>
     * 3.将该deployVM加入到列表中<br/>
     * 4.从当天的请求列表里删除这个请求（可能没法在这个方法内执行）<br/>
     * 5.别忘了更新每天的购买和部署信息（OutPut类）
     *
     * 注意！！！该方法不仅会将请求转换为DeployVM并返回，还会更新目标服务器上的资源！！！
     * @param require
     * @param deployServer 这个参数很重要，关联已经分配的服务器和虚拟机
     * @return
     */
    static DeployVM deployVM(Require require, DeployServer deployServer, String node){
        DeployVM deployVM = new DeployVM(require.getVMId(), require.getVm());
        deployVM.setDeployServer(deployServer);//部署到的服务器
        deployVM.setNode(node);//部署到的节点，A或B

        deployServer.deployVM(deployVM);//部署虚拟机
        return deployVM;
    }

    /**
     * 是否可以将请求部署到服务器的某个节点上
     * 单节点部署需要判断能够部署到A还是B节点，双节点部署只需要判断能不能，可以的话返回AB不可以返回null
     * @param require
     * @param deployServer
     * @return A B AB null
     */
    static String isDeployable(Require require,DeployServer deployServer){
        int nodeType = require.getVm().getNodeType();//当前请求双节点或单节点部署
        int requireCPU = require.getVm().getCPU();//当前请求所需CPU
        int requireMemory = require.getVm().getMemory();//当前请求所需内存

        if (nodeType==0) {//单节点部署
            if (deployServer.getNodeARestCPU()>=requireCPU&&deployServer.getNodeARestMemory()>=requireMemory) return "A";//部署到A节点
            if (deployServer.getNodeBRestCPU()>=requireCPU&&deployServer.getNodeBRestMemory()>=requireMemory) return "B";//部署到B节点
        }else if (nodeType==1){//双节点部署，每个节点提供需求的一半
            if (deployServer.getNodeARestCPU()>=requireCPU/2&&
                    deployServer.getNodeARestMemory()>=requireMemory/2&&
                    deployServer.getNodeBRestCPU()>=requireCPU/2&&
                    deployServer.getNodeBRestMemory()>=requireMemory/2) return "AB";
        }
        return null;//不能部署，资源不够
    }

    /**
     * 请求的平均核内比
     * @param requireList singleNodeList或doubleNodeList，已经按照cpuAndMemRatio升序排序
     */
    static double averageRequiresRatio(List<Require> requireList){
        double averageVmCoreMemRatio=0;//当天请求的平均核内比
        for (Require require:requireList){
            averageVmCoreMemRatio+=require.getVm().getCpuAndMemRatio();
        }
        return averageVmCoreMemRatio/requireList.size();
    }

    /**
     * 奖服务器分类为核内比大于一和小于一的
     */
    static void classifyServer(List<Server> greaterThanOnes, List<Server> lessThanOnes){
        for (Server server:Input.serverMap.values()){
            if (server.getCpuAndMemRatio()>1) greaterThanOnes.add(server);
            else lessThanOnes.add(server);
        }
    }


    /**
     * 将oneDayList按照{@link VisualMachine#getNodeType()}进行分类，拆成单、双节点两个列表
     * @param addOneDayList 一天的add类型请求
     * @param singleNodeList 当日请求的单节点虚拟机列表
     * @param doubleNodeList 当日请求的双节点虚拟机列表
     */
    static void doubleOrSingle(List<Require> addOneDayList,
                               List<Require> singleNodeList,List<Require> doubleNodeList){
        for(Require require:addOneDayList){
            if (require.getVm().getNodeType()==0) singleNodeList.add(require);
            else if (require.getVm().getNodeType()==1) doubleNodeList.add(require);
        }
    }


    /**
     * 产生购买的服务器的编号
     * @return
     */
    static long generateId(){
        return totalId++;
    }
}